\section{Bit commitment}

Bit commitment schéma je protokol pre dvoch účastníkov, kde sa najprv účastník
zaviaže k nejakému bitu (ktorý zatiaľ zostáva utajený pre ostatných) 
a následne po istom čase ho odhalí. Formálne to môžeme definovať takto:

\begin{definicia}
    Majme dve množiny $X,Y$ a funkciu $f\colon \{0,1\} \times X \mapsto Y$,
    ktorú vieme ``ľahko'' počítať.
    Od $f$ požadujeme navyše ešte tieto vlastnosti:
    \begin{itemize}
    \item \emph{vlastnosť utajenia} --
        Zo znalosti $f(b,x)$ je ťažké určiť $b$.

    \item \emph{vlastnosť záväznosti} --
        Je ťažké nájsť $x, y$ také, že $x \neq y$ a 
            $f(0,x) = f(1,y)$.
    \end{itemize}

    Potom bit commitment protokol vyzerá nasledovne:

    \begin{enumerate}
    \item $A$ si zvolí $b \in \{0,1\}$ ku ktorému sa chce zaviazať a
            taktiež si zvolí náhodný prvok $x \inr X$
    \item $A \to B$: $y = f(b,x)$ -- záväzok
    \item $A \to B$: $x$ -- odhalenie, môže prísť po istom čase
    \item $B$ overí, či $y = f(0,x)$ alebo $y = f(1,x)$
    \end{enumerate}
\end{definicia}

\noindent
Tento protokol môžeme realizovať viacerými spôsobmi:

\subsection{Bit commitment pomocou RSA}

Majme nejakú inštanciu RSA systému, teda trojicu $(n,e,d)$,
kde účastník $B$ nepozná súkromný kľúč.
Bit commitment realizujeme nasledovne:
\begin{enumerate}
    \item Záväzok: $A$ si zvolí $x \inr \mathbb{Z}_n^*$, také, že
        $b$ je najmenej významný bit $x$ a pošle 
        $y = x^e \pmod n$.
    \item Odhalenie: $A \send B:x$. Účastník $B$ overí, či
        $x^e \pmod n = y$.
\end{enumerate}

Vlastnosť utajenia je dodržaná, keďže možnosť zistiť $b$
je ekvivalentná rozbitiu RSA schémy.
Vlastnosť záväznosti je tiež dodržaná,
keďže k jednému $y$ existuje iba jedno $x$.
V tomto prípade ide o nepodmienenú bezpečnosť.

\begin{poznamka}
    V krypto I sme si spomínali, že posledný bit je v RSA bezpečný.
    Tak trochu sa tam ale zavádzalo. To, čo sa v skutočnosti dokázalo
    bolo totiž ``Ak vieme zisťovať posledný bit $\then$ vieme lámať
    RSA''. Otázka ale znie, čo ak vieme určovať posledný bit napr. s
    pravdepodobnosťou 51\% bez toho, aby to implikovalo zlomenie celej
    schémy? Odpoveď je, že nevieme, ako dokázali Chor a Goldreich v 
    \cite{rsa-lsb}.
\end{poznamka}

\subsection{Bit commitment pomocou diskrétneho logaritmu}
Majme konečnú grupu $G$ a jej prvky $g, h \in G$,
pričom v tejto grupe nevieme efektívne počítať diskrétny logaritmus.
Zároveň predpokladáme, že
nevieme diskrétny logaritmus $h$ pri základe $g$.
Realizácia funkcie $f(b,x)$ bude nasledovná: 
\begin{equation*}
    f(b,x) = g^x h^b
\end{equation*}

Utajenie je v tomto prípade nepodmienene bezpečné,
lebo existujú $x, y$ také, že: $g^x = g^y h$ 
a teda nevieme jednoznačne určiť $b$ zo znalosti $f(b,x)$.
Vlastnosť záväznosti výplýva z toho, že nepoznáme
diskrétny logaritmus $h$ pri základe $g$.

\todo{BC pomocou kvadratických rezíduí}

\subsubsection{Nepodmienená bezpečnosť a záväznosť}
Môžeme si všimnúť, že sme vedeli dosiahnúť pri jednej vlastnosti 
(utajenie, záväznosť) nepodmienenú bezpečnosť.
Nasledujúca veta hovorí o tom, že nepodmienenú bezpečnosť 
nevieme dosiahnúť pri oboch vlastnostiach.

\begin{veta}
Neexistuje bit commitment schéma, ktorá by garantovala 
nepodmienenú bezpečnosť pri utajení a záväznosti.
\end{veta}

\begin{dokaz}
Sporom. 
Uvažujeme funkciu bit commitment schémy $f(b,x)$.
Ak je táto schéma garantuje nepodmienenú záväznosť, tak
platí $\forall x, y\colon f(x,b_1) = f(y,b_2) \Rightarrow b_1 = b_2$
(teda neexistuje vhodná dvojica
$x, y$ ktorou by sme vedeli porušiť záväzok).
Z toho vyplýva, že keď dostaneme $z = f(x,b)$, tak vieme 
vyskúšaním všetkých možných hodnôt $(x,b)$ určiť vyhovujúce dvojice,
tieto ale musia mať rovnaký commitnutý bit.
Preto táto schéma nemôže garantovať nepodmienené utajenie.
\end{dokaz}
\todo{IDS pre ham cycle pomocou BC}


